// 三数求和问题

const threeSum = function (nums: Array<number>) {
  // 定义一个数组用来存放结果数组
  const result: Array<Array<number>> = [];
  // 开始循环,注意只要循环到len-2就行,因为双指针的左右指针会遍历最后两个数
  const len = nums.length;
  // 对数组进行排序
  nums.sort((a, b) => a - b);
  for (let index = 0; index < len - 2; index++) {
    // index就是固定的一个指针
    // 定义左右指针j 和 k
    let j = index + 1,
      k = len - 1;
    // 如果遇到重复的数字,则跳过去
    if (index > 0 && nums[index] === nums[index + 1]) continue;
    // 开始左右指针的循环
    while (j < k) {
      // 三数之和小于0 ,左指针前进,左边的数小了
      if (nums[index] + nums[j] + nums[k] < 0) {
        // 因为是先进行的左指针前进
        j++;
        // 处理左指针元素重复的情况
        while (j < k && nums[j] === nums[j - 1]) {
          j++;
        }
      } else if (nums[index] + nums[j] + nums[k] > 0) {
        // 三数之和大于00 说明右边的数大了
        k--;
        // 处理右指针元素重复的情况
        while (j < k && nums[k + 1] === nums[k]) {
          k--;
        }
      } else {
        // 得到数字组合
        result.push([nums[index], nums[j], nums[k]]);
        // 左右指针一起前进
        j++;
        k--;
        // 若左指针元素重复，跳过
        while (j < k && nums[j] === nums[j - 1]) {
          j++;
        }

        // 若右指针元素重复，跳过
        while (j < k && nums[k] === nums[k + 1]) {
          k--;
        }
      }
    }
  }
  // 返回结果数组
  return result;
};
